package com.game.pathFinding;

import android.graphics.Point;

import com.game.tiledmap.TiledMap;

public class PathFinding {
	private TiledMap tiledMap;
	private int width;
	private int height;
	
	private int tempt;
	public Point posNext;
	
	private Point goalPos = new Point();
	int VOCUC = 9999;
	int[][] L;
	int[][] matrixgame;
	int[] BelongT;
	int[] Prev;
	int[] Length;
	int[][] indexMatrix;

	public PathFinding(TiledMap map) {
		tiledMap = map;
		width = map.mapWidth;
		height = map.mapHeight;
		initMatrixIndex();
	}

	private void initMatrixL() {
		L = new int[width * height][width * height];
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				if (matrixgame[i][j] == 0) {
					if ((i - 1) >= 0 && matrixgame[i - 1][j] == 0) {
						L[indexMatrix[i][j]][indexMatrix[i - 1][j]] = 1;
						L[indexMatrix[i - 1][j]][indexMatrix[i][j]] = 1;
					}
					if ((i + 1) < height && matrixgame[i + 1][j] == 0) {
						L[indexMatrix[i][j]][indexMatrix[i + 1][j]] = 1;
						L[indexMatrix[i + 1][j]][indexMatrix[i][j]] = 1;
					}
					if ((j - 1) >= 0 && matrixgame[i][j - 1] == 0) {
						L[indexMatrix[i][j - 1]][indexMatrix[i][j]] = 1;
						L[indexMatrix[i][j]][indexMatrix[i][j - 1]] = 1;
					}
					if ((j + 1) <= width && matrixgame[i][j + 1] == 0) {
						L[indexMatrix[i][j + 1]][indexMatrix[i][j]] = 1;
						L[indexMatrix[i][j]][indexMatrix[i][j + 1]] = 1;
					}
				}
			}
		}
	}

	private void initMatrixIndex() {
		indexMatrix = new int[height][width];
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				indexMatrix[i][j] = i * width + j;
			}
		}
	}

	private void initMatrixGame() {
		matrixgame = new int[height][width];
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				matrixgame[i][j] = tiledMap.getCell(i, j);
				if (matrixgame[i][j] < 4) {
					matrixgame[i][j] = 0;
				}
			}
		}
	}

	void Init_Dijkstra(int start) {
		initMatrixGame();
		initMatrixL();
		BelongT = new int[width * height];
		Prev = new int[width * height];
		Length = new int[width * height];
		for (int i = 0; i < width * height; i++) {
			BelongT[i] = 1;
			Prev[i] = -1;
			Length[i] = VOCUC;
		}
		Length[start] = 0;
	}

	private int conver(Point mapIndex) {
		Point tempt = mapIndex;
		return indexMatrix[tempt.x][tempt.y];
	}

	public int Dijkstra_Alg(Point startPos, Point goalPos) {
		Point startP = startPos;
		Point endP = goalPos;
		this.goalPos = goalPos;
		int start = conver(startP);
		int goal = conver(endP);
		Init_Dijkstra(start);
		while (BelongT[goal] == 1) {
			int min = VOCUC;
			int v = -1;
			// Tim min thuoc T:
			for (int i = 0; i < width * height; i++) {
				if (BelongT[i] == 1) {
					if (min > Length[i]) {
						min = Length[i];
						v = i;
					}
				}
			}
			// Loai v ra khoi T:
			if (v == -1) {
				//khong co duong di
				//return -1;
			}	
			BelongT[v] = 0;

			for (int k = 0; k < width * height; k++) {
				if (BelongT[k] != 0 && L[v][k] != 0) {
					if (Length[k] > Length[v] + L[v][k]) {
						Length[k] = Length[v] + L[v][k];
						Prev[k] = v;
					} else if (Length[k] > Length[v] + L[k][v]) {
						Length[k] = Length[v] + L[k][v];
						Prev[k] = v;
					}
				}
			}
		}
		//int cost = 0;
		if (Prev[goal] == -1) {
			// da den dich
			posNext = this.goalPos;
			return 1;
		} else {
			//cost = L[Prev[goal]][goal];
			tempt = 0;
			while (goal != start) {
				tempt = goal;
				goal = Prev[goal];
				if (Prev[goal] == -1) {
					break;
				}
			}
		}
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				if (indexMatrix[i][j] == tempt) {
					posNext = new Point(i, j);
				}
			}
		}
		// tra ve buoc di tip theo
		return 0;
	}
}
